package org.apache.commons.graph.algorithms.scc.sample

import com.gitee.wsl.ext.set.peek
import com.gitee.wsl.ext.set.pop
import com.gitee.wsl.ext.set.push
import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.algorithms.scc.SccAlgorithm

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Applies the classical Cheriyan/Mehlhorn/Gabow's algorithm to find the strongly connected components, if exist.
 * @param <V> the Graph vertices type.
 * @param <E> the Graph edges type.
 * @param <G> the directed graph type
</G></E></V> */
internal class CheriyanMehlhornGabowAlgorithm<V, E>(
    private val graph: DirectedGraph<V, E>
) : SccAlgorithm<V> {
    private val marked: MutableSet<V> = HashSet()

    private val preorder: MutableMap<V, Int> = HashMap()

    private val sscId: MutableMap<V?, Int?> = HashMap()

    private val s = mutableListOf<V>()

    private val p = mutableListOf<V>()

    private var preorderCounter = 0

    private var sscCounter = 0

    private fun dfs(vertex: V) {
        marked.add(vertex)
        preorder[vertex] = preorderCounter++
        s.push(vertex)
        p.push(vertex)
        for (w in graph.getConnectedVertices(vertex)) {
            if (!marked.contains(w)) {
                dfs(w)
            } else if (sscId[w] == null) {
                while (preorder[p.peek()]!! > preorder[w]!!) {
                    p.pop()
                }
            }
        }

        if (p.peek() == vertex) {
            p.pop()
            var w: V? = null
            do {
                w = s.pop()
                sscId[w] = sscCounter
            } while (vertex != w)
            sscCounter++
        }
    }

    /**
     */
    override fun perform(): Set<MutableSet<V>> {
        for (vertex in graph.vertices) {
            if (!marked.contains(vertex)) {
                dfs(vertex)
            }
        }

        val indexedSccComponents: MutableList<MutableSet<V>> = ArrayList()
        for (i in 0..<sscCounter) {
            indexedSccComponents.add(HashSet())
        }

        for (w in graph.vertices) {
            val component = indexedSccComponents[sscId[w]!!]
            component.add(w)
        }

        val scc: MutableSet<MutableSet<V>> = HashSet()
        scc.addAll(indexedSccComponents)
        return scc
    }
}

fun<V, E> SccAlgorithm.Companion.cheriyanMehlhornGabowAlgorithm(graph: DirectedGraph<V, E>):SccAlgorithm<V> = CheriyanMehlhornGabowAlgorithm(graph)